﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace sudokuForm
{
    /// <summary>
    /// 数独
    /// </summary>
    public class Sudoku
    {
        public int[,] Map = new int[9, 9];

        public void Init()
        { }

        public void Init(string mapstr)
        {
            var arr = mapstr.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries);

            for (int j = 0; j < arr.Length; j++)
            {
                var trr = arr[j].Split(' ');
                for (int i = 0; i < trr.Length; i++)
                {
                    Map[i, j] = int.Parse(trr[i]);
                }
            }
        }

        public bool GetResult()
        {
            while (true)
            {
                Start:
                int cX = 0;
                int cY = 0;
                int count = 0;
                List<int> List = null;
                for (int i = 0; i < 9; i++)
                {
                    for (int j = 0; j < 9; j++)
                    {
                        if (Map[i, j] != 0)
                            continue;
                        List<int> rList = new List<int>();
                        rList.AddRange(HA(i));
                        rList.AddRange(WA(j));
                        rList.AddRange(LA(i, j));
                        rList = rList.Distinct().ToList();
                        if (rList.Count == 8)
                        {   // 只有一个可能性，直接填写上
                            for (int k = 1; k <= 9; k++)
                            {
                                if (!rList.Contains(k))
                                {
                                    Map[i, j] = k;
                                    // 每次填写上了，就从头再次检查一遍
                                    goto Start;
                                }
                            }
                        }
                        else
                        { 
                            // 有多个可能性，记录可能性最少（已知值最多）的那个
                            if (rList.Count > count)
                            {
                                cX = i;
                                cY = j;
                                count = rList.Count;
                                List = rList.ToArray().ToList();
                            }

                        }
                        if (rList.Count == 9)
                            return false;
                    }
                }

                if (List != null)
                {   // 到了这里，说明1个可能性的查找失败，对于多个可能性的进行猜测
                    for (int k = 1; k <= 9; k++)
                    {
                        if (List.Contains(k))
                            continue;
                        // 依次假设，看看能否计算出最终结果
                        var ns = this.Clone();
                        ns.Map[cX, cY] = k;
                        if (ns.GetResult())
                        {
                            this.Map = ns.Map;
                            return true;
                        }
                    }
                }
                break;
            }

            return Success();
        }

        private Sudoku Clone()
        {
            Console.Write(".");
            var sdk = new Sudoku();

            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    sdk.Map[i, j] = this.Map[i, j];
                }
            }
            return sdk;
        }
        // 竖行检查
        private int[] WA(int j)
        {
            List<int> list = new List<int>();
            for (int i = 0; i < 9; i++)
            {
                if (Map[i, j] != 0)
                    list.Add(Map[i, j]);
            }
            return list.ToArray();
        }
        // 横行检查
        private int[] HA(int i)
        {
            List<int> list = new List<int>();
            for (int j = 0; j < 9; j++)
            {
                if (Map[i, j] != 0)
                    list.Add(Map[i, j]);
            }
            return list.ToArray();
        }
        // 宫检查
        private int[] LA(int i, int j)
        {
            List<int> list = new List<int>();
            // 计算所在的宫
            var si = i / 3 * 3;
            var sj = j / 3 * 3;
            for (int i1 = 0; i1 < 3; i1++)
            {
                for (int j1 = 0; j1 < 3; j1++)
                {
                    if (Map[si + i1, sj + j1] != 0)
                        list.Add(Map[si + i1, sj + j1]);
                }
            }
            return list.ToArray();
        }

        private bool Success()
        {
            // 依次检查行，竖，宫，是否满足
            for (int i = 0; i < 9; i++)
            {
                var list1 = HA(i);
                if (list1.Distinct().Count() != 9)
                    return false;

                var list2 = WA(i);
                if (list2.Distinct().Count() != 9)
                    return false;
            }


            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    var list = LA(i * 3, j * 3);
                    if (list.Distinct().Count() != 9)
                        return false;
                }
            }

            return true;
        }
    }
}